/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package GraphAlgo;

import java.util.ArrayList;
import java.util.LinkedList;

import Model.Vertex;
import Model.Graph;
import Model.Edge;

/**
 *
 * @author pol
 * 
 * http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices
 */

public class FindAllPathes {

    public FindAllPathes(Graph g) {
        graph = g;
    }

    public ArrayList<LinkedList<Edge>> findAllPathes(Vertex s, Vertex d) {
        start = s;
        destination = d;
        pathFind(start);
//        System.out.println("list - " + listOfPathLists.get(0).size());
        for(Vertex v : listOfPathLists.get(0)) {
            System.out.println(v.getName());
        }
        getEdges();
        return listOfPathEdges;
    }
    
    private void getEdges() {
        for(int i = 0; i<listOfPathLists.size(); i++) {
//            pathEdge.clear();
            for(int j = 0; j<listOfPathLists.get(i).size()-1; j++) {
                Vertex v1 = listOfPathLists.get(i).get(j);
                Vertex v2 = listOfPathLists.get(i).get(j+1);
                pathEdge.add(graph.getEdge(v1, v2));
            }
            listOfPathEdges.add(pathEdge);
        }
    }

    private void pathFind(Vertex c) {
        pathVertex.add(c);
        for(Vertex v : graph.getAdjacentWith(c)) {
            if(v.equals(destination)) {
                pathVertex.add(destination);
                listOfPathLists.add(new LinkedList<Vertex>(pathVertex));
                pathVertex.remove(destination);
            } else if(!pathVertex.contains(v)) {
                pathFind(v);
            }
        }
        pathVertex.remove(c);
    }
    
    private ArrayList<LinkedList<Edge>> listOfPathEdges = new ArrayList<LinkedList<Edge>>();
    private ArrayList<LinkedList<Vertex>> listOfPathLists = new ArrayList<LinkedList<Vertex>>();
    private Graph graph;
    private Vertex start;
    private Vertex destination;
    private LinkedList<Vertex> pathVertex = new LinkedList<Vertex>();
    private LinkedList<Edge> pathEdge = new LinkedList<Edge>();
}
